package com.acwing.lc.part1;

/**
 * @author rkc
 * @date 2022/9/11 10:14
 */
public class LC28实现strStr {

    public int strStr(String s, String p) {
        if (p.length() == 0) return 0;
        int n = s.length(), m = p.length();
        s = ' ' + s;
        p = ' ' + p;
        int[] next = new int[m + 1];
        for (int i = 2, j = 0; i <= m; i++) {
            while (j > 0 && p.charAt(i) != p.charAt(j + 1)) j = next[j];
            if (p.charAt(i) == p.charAt(j + 1)) j++;
            next[i] = j;
        }
        for (int i = 1, j = 0; i <= n; i++) {
            while (j > 0 && s.charAt(i) != p.charAt(j + 1)) j = next[j];
            if (s.charAt(i) == p.charAt(j + 1)) j++;
            if (j == m) return i - m;
        }
        return -1;
    }
}
